package org.sky.algorithm.searchList;

import java.util.Arrays;

/**
 * Description 根据值查找数组中的下标
 *
 * @author fog
 * @date 2021/7/28
 */

public class Search {

    int[] list = new int[]{1, 8, 5, 3, 6, 9, 2};

    /**
     * 线性查找方法
     *
     * @param element 目标元素
     * @return int
     * @author fog
     */
    public int searchIndex(int element) {

        int index = -1;

        for (int i = 0; i < list.length; i++) {
            if (list[i] == element) {
                index = i;
                break;
            }
        }

        return index;
    }

    /**
     * 二分法查找方法
     *
     * @param element 要查找的目标元素
     * @return int
     * @author fog
     */
    public int binarySearch(int element) {

        // 首先要对数组进行排序
        Arrays.sort(list);

        System.out.println(Arrays.toString(list));

        // 记录下标位置
        int index = -1;
        // 开始位置记录
        int begin = 0;
        // 结束位置记录
        int end = list.length - 1;
        // 中间位置记录
        int mid = (begin + end) / 2;

        while (true) {

            // 开始位置在结束位置之后或重合，没有这个元素
            if (begin >= end) {
                return -1;
            }

            // 判断中间位置是不是所要查找的元素
            if (list[mid] == element) {

                index = mid;
                break;
            } else {

                // 不是目标元素
                // 判断这个元素和目标元素的大小，大于目标元素在数组右边，否的话在左边
                if (list[mid] > element) {

                    // 把结束位置向前提一个位置
                    end = mid - 1;
                } else {

                    // 把开始位置向后加一个位置
                    begin = mid + 1;
                }

                // 提取中间位置
                mid = (begin + end) / 2;
            }
        }

        return index;
    }

}
